/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package utiles.datastructure;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;

/**
 * Represents a directed labeled graph. Vertices are represented by their unique
 * labels and labeled edges by means of nested hashtables. Variant of class
 * {@code aima.util.Table}. This version is more dynamic, it requires no
 * initialization and can add new items whenever needed.
 *
 * @author R. Lunde
 * @author Mike Stampone
 */
public class LabeledGraph<VertexLabelType, EdgeLabelType> {

        /**
         * Lookup for edge label information. Contains an entry for every vertex
         * label.
         */
        private final Hashtable<VertexLabelType, Hashtable<VertexLabelType, EdgeLabelType>> globalEdgeLookup;
        /** List of the labels of all vertices within the graph. */
        private final List<VertexLabelType> vertexLabels;

        /** Creates a new empty graph. */
        public LabeledGraph() {
                globalEdgeLookup = new Hashtable<VertexLabelType, Hashtable<VertexLabelType, EdgeLabelType>>();
                vertexLabels = new ArrayList<VertexLabelType>();
        }

        /**
         * Adds a new vertex to the graph if it is not already present.
         *
         * @param v
         *            the vertex to add
         */
        public void addVertex(VertexLabelType v) {
                checkForNewVertex(v);
        }

        /**
         * Adds a directed labeled edge to the graph. The end points of the edge are
         * specified by vertex labels. New vertices are automatically identified and
         * added to the graph.
         *
         * @param from
         *            the first vertex of the edge
         * @param to
         *            the second vertex of the edge
         * @param el
         *            an edge label
         */
        public void set(VertexLabelType from, VertexLabelType to, EdgeLabelType el) {
                Hashtable<VertexLabelType, EdgeLabelType> localEdgeLookup = checkForNewVertex(from);
                localEdgeLookup.put(to, el);
                checkForNewVertex(to);
        }

        /** Handles new vertices. */
        private Hashtable<VertexLabelType, EdgeLabelType> checkForNewVertex(
                        VertexLabelType v) {
                Hashtable<VertexLabelType, EdgeLabelType> result = globalEdgeLookup
                                .get(v);
                if (result == null) {
                        result = new Hashtable<VertexLabelType, EdgeLabelType>();
                        globalEdgeLookup.put(v, result);
                        vertexLabels.add(v);
                }
                return result;
        }

        /**
         * Removes an edge from the graph.
         *
         * @param from
         *            the first vertex of the edge
         * @param to
         *            the second vertex of the edge
         */
        public void remove(VertexLabelType from, VertexLabelType to) {
                Hashtable<VertexLabelType, EdgeLabelType> localEdgeLookup = globalEdgeLookup
                                .get(from);
                if (localEdgeLookup != null)
                        localEdgeLookup.remove(to);
        }

        /**
         * Returns the label of the edge between the specified vertices, or null if
         * there is no edge between them.
         *
         * @param from
         *            the first vertex of the ege
         * @param to
         *            the second vertex of the edge
         *
         * @return the label of the edge between the specified vertices, or null if
         *         there is no edge between them.
         */
        public EdgeLabelType get(VertexLabelType from, VertexLabelType to) {
                Hashtable<VertexLabelType, EdgeLabelType> localEdgeLookup = globalEdgeLookup
                                .get(from);
                return localEdgeLookup == null ? null : localEdgeLookup.get(to);
        }

        /**
         * Returns the labels of those vertices which can be obtained by following
         * the edges starting at the specified vertex.
         */
        public List<VertexLabelType> getSuccessors(VertexLabelType v) {
                List<VertexLabelType> result = new ArrayList<VertexLabelType>();
                Hashtable<VertexLabelType, EdgeLabelType> localEdgeLookup = globalEdgeLookup
                                .get(v);
                if (localEdgeLookup != null)
                        result.addAll(localEdgeLookup.keySet());
                return result;
        }

        /** Returns the labels of all vertices within the graph. */
        public List<VertexLabelType> getVertexLabels() {
                return vertexLabels;
        }

        /** Checks whether the given label is the label of one of the vertices. */
        public boolean isVertexLabel(VertexLabelType v) {
                return globalEdgeLookup.get(v) != null;
        }

        /** Removes all vertices and all edges from the graph. */
        public void clear() {
                vertexLabels.clear();
                globalEdgeLookup.clear();
        }
}
